/**
 * 
 */
package tree.passed2;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author michael
 *
 */
public class BinaryTreeRightSideView {

	/**
	Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.
	
	For example:
	Given the following binary tree,
	   1            <---
	 /   \
	2     3         <---
	 \     \
	  5     4       <---
	You should return [1, 3, 4].
	 */
	/**
	 * Definition for binary tree
	 */
	 public class TreeNode {
	     int val;
	     TreeNode left;
	     TreeNode right;
	     TreeNode(int x) { val = x; }
	 }
	 public List<Integer> rightSideView(TreeNode root) {
		 List<Integer> result = new LinkedList<>();
		 if (root == null)
			 return result;

		 Queue<TreeNode> queue = new LinkedList<>();
		 queue.offer(root);
		 while (!queue.isEmpty()) {
			 final int size = queue.size();
			 for (int i = 0; i < size; i++) {
				 TreeNode node = queue.poll();
				 if (i == size - 1)
					 result.add(node.val);
				 if (node.left != null)
					 queue.offer(node.left);
				 if (node.right != null)
					 queue.offer(node.right);
			 }
		 }

		 return result;
	 }
	
	/**
	 * 
	 */
	public BinaryTreeRightSideView() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
